package com.toutiao.issue

import scala.collection.mutable.{ HashMap => HMap }
import scala.collection.mutable.ArrayBuffer

import org.apache.log4j.Logger

class InvertIndex[T] {

  private val _log = Logger.getLogger(this.getClass.getName)

  val M = new HMap[T, ArrayBuffer[Int]]

  private 
  def _binarySearch(zs: ArrayBuffer[Int], start: Int, len: Int, key: Int) = {
    var high = start + len
    var low = start - 1

    while (high - low > 1) {
      val guess = (high + low) / 2
      if (zs(guess) < key)
        low = guess
      else
        high = guess
    }

    high
  }

  def insert(n: Int, m: Array[T]) {
    for (v <- m) {
      val zs = M.getOrElse(v, new ArrayBuffer[Int])
      if (zs.size == 0 || zs(zs.size - 1) <= n) {
        zs += n
      } else {
        val i = _binarySearch(zs, 0, zs.size, n)
        zs.insert(i, n)
      }
      M(v) = zs
    }
  }

// 20:01:46,068 ERROR com.toutiao.rees.InvertIndex:51 - 妇幼保健 ArrayBuffer(2351685, 2365197, 2383437, 2431533, 2480349)
// 20:01:46,068 ERROR com.toutiao.rees.InvertIndex:52 - 2524677 妇幼保健 5  
  
  def remove(n: Int, m: Array[T]) {
    for (v <- m if M.contains(v)) {
      val zs = M(v)
      val i = _binarySearch(zs, 0, zs.size, n)
      if (i >= 0 && i < zs.size) {
        zs.remove(i)
      } else {
        // 已经删过了
        _log.error(v + " " + M(v))
        _log.error(n + " " + v + " " + i)
      }
      if (zs.size == 0) {
        M.remove(v)
      } else {
        M(v) = zs
      }
    }
  }

  def process(m: Array[T]): Array[Int] = {
    val A = new ArrayBuffer[Int]
    val vs = m.filter(M.contains(_))
    for (v <- vs) {
      for (n <- M(v)) {
        A += n
      }
    }
    A.toArray
  }

  def contains(z: T) = {
    M.contains(z)
  }

  def apply(z: T): ArrayBuffer[Int] = {
    M(z)
  }

}
